package demo20;

import java.util.LinkedList;

/*
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

    有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
 */
public class Test {
    public static void main(String[] args) {

        String str = "{[]}";
        System.out.println(isValid(str));


    }


    public static boolean isValid(String s) {
        //定义一个栈，用来存左字符，当扫描到右字符的时候再拿栈元素比较
        LinkedList<Character> list = new LinkedList<>();
        //将字符串转换为字符数组
        char[] chs = s.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            switch (chs[i]){
                //左字符都放进栈内
                case '(':{
                    list.addFirst(chs[i]);
                    continue;
                }
                case '[':{
                    list.addFirst(chs[i]);
                    continue;
                }
                case '{':{
                    list.addFirst(chs[i]);
                    continue;
                }
                //右字符对栈内最上面的元素进行判断
                case ')':{
                    if(list.size() != 0 && list.getFirst() == '('){
                        list.removeFirst();
                    }else{
                        //不符合要求，直接返回false
                        return false;
                    }
                    continue;
                }
                case ']':{
                    if(list.size() != 0 && list.getFirst() == '['){
                        list.removeFirst();
                    }else{
                        //不符合要求，直接返回false
                        return false;
                    }
                    continue;
                }
                case '}':{
                    if(list.size() != 0 && list.getFirst() == '{'){
                        list.removeFirst();
                    }else{
                        //不符合要求，直接返回false
                        return false;
                    }
                    continue;
                }
            }
        }
        //整个循环下来，如果list中还存有没配队的左字符，那就返回false
        return list.size() == 0 ? true : false;
    }
}
